﻿//给你一个整数数组 nums ，判断是否存在三元组[nums[i], nums[j], nums[k]] 
//满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
//请你返回所有和为 0 且不重复的三元组。
//
//注意：答案中不可以包含重复的三元组。
//
//输入：nums = [-1, 0, 1, 2, -1, -4]
//输出： [[-1, -1, 2], [-1, 0, 1]]
//解释：
//nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
//nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
//nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
//不同的三元组是[-1, 0, 1] 和[-1, -1, 2] 。
//注意，输出的顺序和三元组的顺序并不重要。
//
//输入：nums = [0, 1, 1]
//输出：[]
//解释：唯一可能的三元组和不为 0 。
//
//输入：nums = [0, 0, 0]
//输出： [[0, 0, 0]]
//解释：唯一可能的三元组和为 0 。
//
//提示：
//	3 <= nums.length <= 3000
//	- 10^5 <= nums[i] <= 10^5

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        // 1.排序

        sort(nums.begin(), nums.end());
        // 2. ⽤双指针解决问题

        int n = nums.size();
        for (int i = 0; i < n;) // 固定数a
        {
            if (nums[i] > 0)
                break; // ⼩优化

            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
                else {
                    ret.push_back({ nums[i], nums[left], nums[right] });
                    left++, right--;
                    // 去重操作left和right
                    while (left < right && nums[left] == nums[left - 1])
                        left++;
                    while (left < right && nums[right] == nums[right + 1])
                        right--;
                }
            }
            // 去重i
            i++;
            while (i < n && nums[i] == nums[i - 1])
                i++;
        }
        return ret;
    }
};